/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Compare {
        bool operator()(const pair<ListNode*, int>& p1,
                        const pair<ListNode*, int>& p2) {
            return p1.second > p2.second;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return nullptr;
        priority_queue<pair<ListNode*, int>, vector<pair<ListNode*, int>>,
                       Compare>
            q;
        for (const auto& e : lists) {
            ListNode* cur = e;
            while (cur) {
                q.push({cur, cur->val});
                cur = cur->next;
            }
        }
        ListNode* head = nullptr;
        if (!q.empty()) {
            head = q.top().first;
            q.pop();
        }
        ListNode* tail = head;
        while (!q.empty()) {
            ListNode* cur = q.top().first;
            q.pop();
            tail->next = cur;
            tail = cur;
        }
        if (tail)
            tail->next = nullptr;
        return head;
    }
};